public class MyDinkedList {
    //这是一个双向链表的实现
    //先创建一个节点
    static class Node {
        public String val;
        public Node prev=null;
        public Node next=null;
        public Node(String val) {    //构造函数
            this.val = val;
        }
    }

    //使用head表示头结点
    private Node head=null;
    //使用tail表尾节点
    private Node tail=null;


    @Override
    public String toString() {
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append("[");
        for(Node cur=head;cur!=null;cur=cur.next){
            stringBuilder.append(cur.val);
            if(cur.next!=null){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }


    //获取链表长度
    public int size(){
        int size=0;
        for(Node cur=head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
    }


    //头插
    public void addFirst(String val){
        Node newNode=new Node(val);
        if(head==null){
            head=tail=newNode;
            return;
        }
        newNode.next=head;
        head.prev=newNode;
        head=newNode;
    }

    public void addLast(String val){
        Node newNode=new Node(val);
        if(tail==null){
            head=tail=newNode;
            return;
        }
        tail.next=newNode;
        newNode.prev=tail;
        tail=newNode;
    }


    public void add(int index,String val){
        if(index<0||index>size()){
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        if(index==0){
            addFirst(val);
            return;
        }
        if(index==size()){
            addLast(val);
            return;
        }
        Node newNode=new Node(val);
        Node cur=head;
        for(int i=0;i<index-1;i++){
            cur=cur.next;
        }
        newNode.next=cur.next;
        newNode.prev=cur;
        cur.next.prev=newNode;
        cur.next=newNode;
    }


    public boolean contains(String val){
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.val.equals(val)){
                return true;
            }
        }
        return false;
    }


    public int indexOf(String val){
        int index=0;
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.val.equals(val)){
                return index;
            }
            index++;
        }
        return -1;
    }


    public void removeFirst(){
        if(head==null){
            return;
        }
        if(head.next==null){
            head=tail=null;
            return;
        }
        head=head.next;
        head.prev=null;
    }


    public void removeLast(){
        if(tail==null){
            return;
        }
        if(tail.prev==null){
            head=tail=null;
            return;
        }
        tail=tail.prev;
        tail.next=null;
    }

    public void remove(int index){
        if(index<0||index>=size()){
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        if(index==0){
            removeFirst();
            return;
        }
        if(index==size()-1){
            removeLast();
            return;
        }
        Node cur=head;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.prev.next=cur.next;
        cur.next.prev=cur.prev;
    }


    public void remove(String val){
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.val.equals(val)){
                if(cur.prev==null){
                    removeFirst();
                }else if(cur.next==null){
                    removeLast();
                }else{
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;
                }
                return;
            }
        }
        return;
    }

    public void clear(){
        head=tail=null;
    }



    public static void main(String[] args) {
        //test1();
//        test2();
//        test3();
//        test4();
        test5();
    }

    private static void test5() {
        MyDinkedList list=new MyDinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list);
        list.removeFirst();
        System.out.println(list);
        list.removeLast();
        System.out.println(list);
        list.remove(1);
        System.out.println(list);
        list.remove("b");
        System.out.println(list);

    }

    private static void test4() {
        MyDinkedList list=new MyDinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list);
        System.out.println(list.contains("a"));
        System.out.println(list.contains("e"));
        System.out.println(list.indexOf("b"));
        System.out.println(list.indexOf("e"));
    }

    private static void test3() {
        MyDinkedList list=new MyDinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list);
    }

    private static void test2() {
        MyDinkedList list=new MyDinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        System.out.println(list);
    }


    private static void test1(){
        MyDinkedList list=new MyDinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        System.out.println(list);
    }




}
